package com.atguigui.leetcode1;

/**
 * 1043.分隔数组以得到最大和
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/4/19 9:02
 */
public class P1043PartitionArrayForMaximumSum {
    public static void main(String[] args) {
        Solution solution = new P1043PartitionArrayForMaximumSum().new Solution();
        // TO TEST
    }

    class Solution {
        public int maxSumAfterPartitioning(int[] arr, int k) {
            int n = arr.length;
            int[] d = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                //前一个数
                int maxValue = arr[i - 1];
                //
                for (int j = i - 1; j >= 0 && j >= i - k; j--) {
                    d[i] = Math.max(d[i], d[j] + maxValue * (i - j));
                    if (j > 0) {
                        maxValue = Math.max(maxValue, arr[j - 1]);
                    }
                }
            }
            return d[n];
        }
    }
}
